//给定一个单链表 L 的头节点 head ，单链表 L 表示为： 
//
// L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为： 
//
// L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 
//
// 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入: head = [1,2,3,4]
//输出: [1,4,2,3] 
//
// 示例 2: 
//
// 
//
// 
//输入: head = [1,2,3,4,5]
//输出: [1,5,2,4,3] 
//
// 
//
// 提示： 
//
// 
// 链表的长度范围为 [1, 5 * 10⁴] 
// 1 <= node.val <= 1000 
// 
//
// 
//
// 
// 注意：本题与主站 143 题相同：https://leetcode-cn.com/problems/reorder-list/ 
//
// Related Topics 栈 递归 链表 双指针 👍 70 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class SolutionOffer2_026 {
    public void reorderList(ListNode head) {
        ListNode midListNode = getMidListNode(head);
        ListNode l1 = head;
        ListNode l2 = midListNode.next;
        midListNode.next = null;
        l2 = reverse(l2);
        merge(l1, l2);
    }

    public ListNode getMidListNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur != null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode merge(ListNode head1, ListNode head2){
        ListNode newHead = new ListNode(0);
        newHead.next = head1;
        ListNode tmp = newHead.next;
        while(head1 != null && head2 != null){
            if(tmp == head1){
                tmp.next = head2;
                head1 = head1.next;
            }
            if(tmp == head2){
                tmp.next = head1;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        return tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
